export class myQuadTree {  
    bounds:Rect;
    max_objects:number;
    max_levels:number;
    level:number;
    objects:any[]
    nodes:any[]
    //构造函数 bounds为分区，max_objects为
    constructor(bounds:Rect, max_objects:number=10, max_levels:number=4, level:number=0){
        this.bounds=bounds
        this.max_objects=max_objects
        this.max_levels=max_levels
        this.level=level
        this.objects=[]
        this.nodes=[]
    }
    //分割象限
    split(){
        let nextLevel=this.level+1;
        let subwidth =this.bounds.width/2;
        let subHeight=this.bounds.height/2;
        let x = this.bounds.x;
        let y = this.bounds.y;

        //以1/2节点宽度/和1/2节点高度为原点划分象限
        //第一象限节点
        this.nodes.push(new myQuadTree({
            x:x+subwidth,
            y:y+subHeight,
            width:subwidth,
            height:subHeight
        }, this.max_objects, this.max_levels, nextLevel))
        //第二象限节点
        this.nodes.push(new myQuadTree({
            x:x,
            y:y+subHeight,
            width:subwidth,
            height:subHeight
        }, this.max_objects, this.max_levels, nextLevel))
        //第三象限节点
        this.nodes.push(new myQuadTree({
            x:x,
            y:y,
            width:subwidth,
            height:subHeight
        }, this.max_objects, this.max_levels, nextLevel))
        //第四象限节点
        this.nodes.push(new myQuadTree({
            x:x+subwidth,
            y:y,
            width:subwidth,
            height:subHeight
        }, this.max_objects, this.max_levels, nextLevel))  
    }
    //判断传入范围在当前四叉树节点的哪个象限，0-第一象限，1-第二象限，2-第三象限，3-第四象限
    getIndex(rect){
        let indexes=[]
        let originPointX=this.bounds.x+(this.bounds.width/2)
        let originPointY = this.bounds.y+(this.bounds.height/2)
        let topOrBottom= rect.y<originPointY
        let leftOrRight = rect.x<originPointX
        let rangeBeyondV = rect.x+rect.width>originPointX
        let rangeBeyondH = rect.y+rect.height>originPointY
        
        if(rangeBeyondH && rangeBeyondV){
            indexes.push(0)
        }

        if(leftOrRight && rangeBeyondH){
            indexes.push(1)
        }

        if(leftOrRight && topOrBottom){
            indexes.push(2)
        }
        
        if(topOrBottom &&rangeBeyondV){
            indexes.push(3)
        }
        return indexes
    }
    //插入节点
    insert(rect){
        let i =0
        let indexes
        //当四叉树节点内的孩子节点不为空时，即有孩子节点
        if(this.nodes.length){
            //判断范围节点所处象限
            indexes = this.getIndex(rect)
            for(i=0;i<indexes.length;i++){
                //插入对应象限
                this.nodes[indexes[i]].insert(rect)
            }
            return;
        }
        //基本的插入操作，将范围节点范围插入当前四叉树的objects数组中
        this.objects.push(rect)
        //当objects数组的长度大于限定存储空间后 并且当前level小于设定四叉树的总层数，当分级数超过最大的层数后便不再分级处理
        if(this.objects.length > this.max_objects &&this.level<this.max_levels){
            //如果当前的四叉树节点未分级，则对内部范围节点执行一次分级
            //即产生下一层的空间但不填充
            if(!this.nodes.length){
                this.split()
            }
            //根据当前四叉树节点内包含的范围结点进行象限划分
            //并将范围节点放入当前四叉树节点的所属象限内
            for(i=0;i<this.objects.length;i++){
                indexes = this.getIndex(this.objects[i])
                for(let k =0;k<indexes.length;k++){
                    this.nodes[indexes[k]].insert(this.objects[i])
                }
            }
            //划分完毕后当前四叉树节点不存留任何节点数据单纯变为一个指向四个孩子结点的父节点
            this.objects=[];
        }
    }
    //检测碰撞
    retrieve(rect){
        let indexes = this.getIndex(rect)
        let returnObjects = this.objects
        //当前四叉树节点分区不为空
        //循环递归检测
        if(this.nodes.length){
            for(let i=0;i<indexes.length;i++){
                returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(rect));
            }
        }
        //返回内部节点
        returnObjects = returnObjects.filter(function(item, index) {
            return returnObjects.indexOf(item) >= index;
        });
     
        return returnObjects;
    }
    //清除内部节点
    clear(){
        this.objects = [];
        
        for(var i=0; i < this.nodes.length; i++) {
            if(this.nodes.length) {
                this.nodes[i].clear();
              }
        }

        this.nodes = [];
    }
}
//矩形范围接口
interface Rect{
    x:number,
    y:number,
    width:number,
    height:number
}
class nodeRect implements Rect{
    node:Node
    x:number
    y:number
    width:number
    height:number
}